/*
    
平衡二叉树是一种二叉排序树，它的左右子树高度差不超过1。这种结构在执行插入和删除操作后，会自动调整，以确保树的平衡性。常见的平衡二叉树有AVL树和红黑树。

实现AVL树
AVL树是一种自平衡二叉排序树，在插入或删除节点后，可能会进行旋转操作，以保持平衡。AVL树的每个节点都记录了其高度，用于计算平衡因子。

下面是一个AVL树的C语言实现示例，包含插入、左旋、右旋、获取高度和计算平衡因子等操作。
*/

#include <stdio.h>
#include <stdlib.h>

// 定义AVL树节点结构
typedef struct Node {
    int data;  // 节点值
    struct Node* left;  // 左子节点
    struct Node* right;  // 右子节点
    int height;  // 节点高度
} Node;

// 获取节点高度
int height(Node* node) {
    return node ? node->height : 0;
}

// 计算平衡因子
int getBalance(Node* node) {
    return node ? height(node->left) - height(node->right) : 0;
}

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode) {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->height = 1;  // 初始高度
    }
    return newNode;
}

// 左旋
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // 旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));

    return y;  // 新的根节点
}

// 右旋
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));

    return x;  // 新的根节点
}

// 插入节点并保持平衡
Node* insert(Node* node, int data) {
    if (node == NULL) {  // 如果节点为空，创建新节点
        return createNode(data);
    }

    if (data < node->data) {
        node->left = insert(node->left, data);  // 插入到左子树
    } else if (data > node->data) {
        node->right = insert(node->right, data);  // 插入到右子树
    } else {
        return node;  // 不允许重复插入
    }

    // 更新高度
    node->height = 1 + (height(node->left) > height(node->right) ? height(node->left) : height(node->right));

    // 检查平衡
    int balance = getBalance(node);

    // 左左情况
    if (balance > 1 && data < node->left->data) {
        return rightRotate(node);
    }

    // 右右情况
    if (balance < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // 左右情况
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右左情况
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;  // 返回当前节点
}

// 前序遍历
void preOrder(Node* node) {
    if (node) {
        printf("%d ", node->data);
        preOrder(node->left);
        preOrder(node->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 10);
    root = insert(root, 25);

    printf("前序遍历: ");
    preOrder(root);
    printf("\n");

    return 0;
}
